网络流24题

一.最大流问题

1.P2764 最小路径覆盖问题

首先每个点用一条边覆盖，为了使路径尽可能少，我们要连接一些路径。

将每个点拆成两个点 $x_i,y_i$ ，对于 $u \rightarrow v$ 这条边，连接 $x_u,y_v$ 并将容量设为 $1$，如果这条边有流则表示将 $u,v$ 的路径合并。

然后连接 $S \rightarrow x_i,y_i\rightarrow T$，容量也设为 $1$ （要求顶点不相交，每个点只能连接一次）

最后图的最大流便是连接的最大数量，答案为 $n-\text{最大流}$。

方案直接记录后继节点就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 300 , MAXM = 7000;
struct node {
	int v , flow , nxt;
}Graph[ 2 * MAXM + 5 ];
int tot = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ tot ] = { v , f , Head[ u ] };
	Head[ u ] = tot;
}

int n , m , s , t;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flow;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}

int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flow;
		cur[ u ] = i;
		if( flw > 0 && lev[ u ] < lev[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
				if( u != s && v > n ) sta[ v - n ] = 1;
				nxt[ u ] = v;
				return mf;
			}
		}
	}
	return 0;
}

int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	for( int i = 1 ; i <= n ; i ++ )
		if( !sta[ i ] ) {
			printf("%d", i );
			int u = i;
			while( nxt[ u ] && nxt[ u ] != t ) {
				printf(" %d", nxt[ u ] - n );
				u = nxt[ u ] - n;
			}
			printf("\n");
		}
	return Maxf;
}

int main( ) {
	scanf("%d %d",&n,&m);
	s = 2 * n + 1 , t = 2 * n + 2;
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		Add_Edge( u , v + n , 1 );
		Add_Edge( v + n , u , 0 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( s , i , 1 ) , Add_Edge( i , s , 0 );
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( i + n , t , 1 ) , Add_Edge( t , i + n , 0 );
    
	
	printf("%d\n", n - Dinic( s , t ) );
	return 0; 
} 

变式：P5769 [JSOI2016]飞机调度 题解